/*
 * Graph_bfs.cpp
 *
 *  Created on: 31.03.2014
 *      Author: Medvedeva Anna
 */

#include <list>
#include <stack>
#include <deque>
#include <vector>
#include <iostream>
#include "Graph.h"

using namespace std ;

void Graph::bfs(int vertex)
{
	cout << "BFS:\n";
	deque <int> bfsVertices;
	vector <int> bfsColors(numbVertices,0);
	make_grey(bfsColors,vertex);
	bfsVertices.push_back(vertex);
	while (!bfsVertices.empty()) {
		int curVertex = *(bfsVertices.begin());
		bfsVertices.pop_front();
		add_neighbors(curVertex, bfsColors, bfsVertices);
		make_black(bfsColors, curVertex);
		cout <<  curVertex + 1 << " " ;
	}
	cout << endl;
}

int Graph::add_neighbors (int vertex, vector<int> &colors, deque <int > &bfsVertices)
{
	if (list_edges.empty()) {
		for (int i = 0 ; i < numbVertices; i++) {
			if (connect_matrix[vertex][i]) {
				if (colors[i] == 0) {
					make_grey(colors, i);
					bfsVertices.push_back(i);
				}
			}
		}
	} else {
		list<int>::iterator i = list_edges[vertex].begin();
		while(i != list_edges[vertex].end()){
			int curVert = *i;
			if (colors[curVert] == 0) {
				make_grey(colors, curVert);
				bfsVertices.push_back(curVert);
			}
			i++;
		}
	}
	return 1;
}




